//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
//
// 
//
// 示例 1： 
//
// 
//输入：l1 = [1,2,4], l2 = [1,3,4]
//输出：[1,1,2,3,4,4]
// 
//
// 示例 2： 
//
// 
//输入：l1 = [], l2 = []
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：l1 = [], l2 = [0]
//输出：[0]
// 
//
// 
//
// 提示： 
//
// 
// 两个链表的节点数目范围是 [0, 50] 
// -100 <= Node.val <= 100 
// l1 和 l2 均按 非递减顺序 排列 
// 
// Related Topics 递归 链表 👍 1981 👎 0

package leetcode.editor.cn;


public class _21_MergeTwoSortedLists {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void show(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    public static void main(String[] args) {
        int[] nums_1 = {1, 3, 5};
        for (int i = 0, j = nums_1.length - 1; i < j; i++, j--) {
            int tmp = nums_1[i];
            nums_1[i] = nums_1[j];
            nums_1[j] = tmp;
        }
        ListNode head_1 = new ListNode(nums_1[0], null);
        ListNode tmp = null;
        for (int i = 1; i < nums_1.length; i++) {
            tmp = new ListNode(nums_1[i], head_1);
            head_1 = tmp;
        }

        int[] nums_2 = {2, 4, 6};
        for (int i = 0, j = nums_2.length - 1; i < j; i++, j--) {
            int temp = nums_2[i];
            nums_2[i] = nums_2[j];
            nums_2[j] = temp;
        }
        ListNode head_2 = new ListNode(nums_2[0], null);
        ListNode temp = null;
        for (int i = 1; i < nums_2.length; i++) {
            tmp = new ListNode(nums_2[i], head_2);
            head_2 = tmp;
        }
        Solution solution = new _21_MergeTwoSortedLists().new Solution();
        ListNode listNode = solution.mergeTwoLists(head_1, head_2);
        show(listNode);
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if (l1 == null || l2 == null) {
                return l1 == null ? l2 : l1;
            }
            if (l1.val <= l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            } else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }

        public ListNode mergeTwoLists_3(ListNode l1, ListNode l2) {
            if (l1 == null || l2 == null) {
                return l1 == null ? l2 : l1;
            }
            ListNode head = l1.val < l2.val ? l1 : l2;

            ListNode cur1 = l1 == head ? l1 : l2;
            ListNode cur2 = l1 == head ? l2 : l1;

            ListNode pre = null;        // cur1的前驱节点

            while (cur1 != null && cur2 != null) {
                if (cur1.val <= cur2.val) {
                    // 第一次肯定走这里
                    pre = cur1;
                    cur1 = cur1.next;
                } else {
                    pre.next = cur2;
                    cur2 = cur1;
                    cur1 = pre.next;
                }
            }
            pre.next = cur2;
            return head;
        }
        public ListNode mergeTwoLists_2(ListNode l1, ListNode l2) {
            if (l1 == null || l2 == null) {
                return l1 == null ? l2 : l1;
            }
            // 合并后头节点
            ListNode head = l1.val < l2.val ? l1 : l2;

            ListNode cur1 = head == l1 ? l1 : l2;
            ListNode cur2 = head == l1 ? l2 : l1;

            ListNode pre = null;    // cur1前一个节点
            ListNode next = null;   // cur2后一个节点


//            ListNode tmp = null;
//            while (cur1 != null && cur2 != null) {
//                if (cur1.val <= cur2.val) {
//                    pre = cur1;
//                    cur1 = cur1.next;
//                } else {
//                    tmp = cur2;
//                    cur2 = cur2.next;
//                    tmp.next = cur1;
//                    pre.next = tmp;
//                }
//            }
//            pre.next = cur1 == null ? cur2 : cur1;
//            return head;

//            while (cur1 != null && cur2 != null) {
//                if (cur1.val <= cur2.val) {
//                    pre = cur1;
//                    cur1 = cur1.next;
//                } else {
//                    next = cur2.next;
//                    pre.next = cur2;
//                    cur2.next = cur1;
//                    pre = cur2;
//                    cur2 = next;
//                }
//            }
//            pre.next = cur1 == null ? cur2 : cur1;
//            return head;

            while (cur1 != null && cur2 != null) {
                if (cur1.val <= cur2.val) {
                    pre = cur1;
                    cur1 = cur1.next;
                } else {
                    pre.next = cur2;
                    cur2 = cur1;
                    cur1 = pre.next;
                }
            }
            pre.next = cur2;
            return head;
        }
    }
    public static void add(ListNode l, ListNode node) {

    }
//leetcode submit region end(Prohibit modification and deletion)

}